﻿namespace Leetcode.N0327;
public class Solution
{
    public int CountRangeSum(int[] nums, int lower, int upper)
    {
        var preSums = new long[nums.Length + 1];
        for (int i = 1; i <= nums.Length; i++)
        {
            preSums[i] = preSums[i - 1] + nums[i - 1];
        }

        return this.CountRangeSum(preSums, 0, preSums.Length - 1, lower, upper);
    }

    protected internal int CountRangeSum(long[] nums, int left, int right, int lower, int upper)
    {
        if (left == right)
        {
            return 0;
        }

        var middle = left + (right - left) / 2;
        var resultLeft = this.CountRangeSum(nums, left, middle, lower, upper);
        var resultRight = this.CountRangeSum(nums, middle + 1, right, lower, upper);

        var result = resultLeft + resultRight;

        result += this.CountRange(nums, lower, upper, left, middle, right);

        this.MergeSortedNums(nums, left, middle, right);

        return result;
    }


    /// <summary>
    /// 计算当前范围满足条件的数量
    /// </summary>
    private int CountRange(long[] nums, int lower, int upper, int left, int middle, int right)
    {
        var i = left;
        var lowerIndex = middle + 1;
        int upperIndex = middle + 1;
        var count = 0;
        while (i <= middle && lowerIndex <= right)
        {
            while (lowerIndex <= right && nums[lowerIndex] - nums[i] < lower) lowerIndex++;

            while (upperIndex <= right && nums[upperIndex] - nums[i] <= upper) upperIndex++;

            count += upperIndex - lowerIndex;
            i++;
        }

        return count;
    }

    /// <summary>
    /// 归并排序合并左右两边已经排序好的元素
    /// </summary>
    /// <param name="nums"></param>
    /// <param name="left">左边的序号</param>
    /// <param name="middle">中间的序号</param>
    /// <param name="right">右边的序号</param>
    private void MergeSortedNums(long[] nums, int left, int middle, int right)
    {
        var merged = new long[right - left + 1];
        var leftFrom = left;
        var rightFrom = middle + 1;
        var mergedIndex = 0;
        while (leftFrom <= middle || rightFrom <= right)
        {
            if (leftFrom <= middle && rightFrom <= right)
            {
                if (nums[leftFrom] <= nums[rightFrom])
                {
                    merged[mergedIndex++] = nums[leftFrom++];
                }
                else
                {
                    merged[mergedIndex++] = nums[rightFrom++];
                }
            }
            else if (leftFrom > middle)
            {
                merged[mergedIndex++] = nums[rightFrom++];
            }
            else
            {
                merged[mergedIndex++] = nums[leftFrom++];
            }
        }

        for (int i = 0; i < merged.Length; i++)
        {
            nums[left + i] = merged[i];
        }
    }
}
